package exhaust;

import java.util.ArrayList;
import java.util.List;

/**
 * 和尚和妖怪同时过河问题
 * <pre>
 *     有三个和尚和三个妖怪要过河，只有一条小船，小船一次只能带2个人。同时，无论在河的两岸，只要妖怪的数量大于和尚的数量，妖怪就会吃掉和尚。问：怎么过河
 * </pre>
 * Created by donghongli on 2017-03-23.
 */
public class MonkAcrossTheRiver {

    //总共过河的方法数量
    public static int count = 0;

    public static void main(String[] args) {

        List<Status> statusList = new ArrayList<>();
        Status startStatus = new Status();
        statusList.add(startStatus);
        searchResult(statusList);
        System.out.println(count);
    }

    /**
     * 遍历过河状态
     * @param statusList
     */
    private static void searchResult(List<Status> statusList) {
        //当前状态
        Status status = statusList.get(statusList.size() - 1);
        if (checkIsResult(statusList, status)) {
            return;
        }
        for (BoatAction boatAction : BoatAction.values()) {
            if (!canMove(status, boatAction)) {
                continue;
            }
            int[] newNums = new int[4];
            for (int i = 0; i < status.nums.length; i++) {
                newNums[i] = status.nums[i] + boatAction.numChanges[i];
            }
            Status newStatus = new Status(newNums, boatAction.boatStatus);
            if (checkValidStatus(newStatus) || checkIsHaveSameStatus(newStatus, statusList)) {
                continue;
            }
            statusList.add(newStatus);
            searchResult(statusList);
            statusList.remove(newStatus);
        }
    }

    /**
     * 检查状态是否为有效状态
     * @param newStatus
     * @return
     */
    private static boolean checkValidStatus(Status newStatus) {
        if (newStatus.nums[0] != 0 && newStatus.nums[0] < newStatus.nums[1]) {
            return true;
        }
        return newStatus.nums[2] != 0 && newStatus.nums[2] < newStatus.nums[3];
    }

    /**
     * 检查是否有相同状态
     * @param newStatus
     * @param statusList
     * @return
     */
    private static boolean checkIsHaveSameStatus(Status newStatus, List<Status> statusList) {
        for (Status status : statusList) {
            if (newStatus.nums[0] == status.nums[0] && newStatus.nums[1] == status.nums[1]
                && newStatus.nums[2] == status.nums[2] && newStatus.nums[3] == status.nums[3]
                && newStatus.boatStatus == status.boatStatus) {
                return true;
            }
        }
        return false;
    }

    private static boolean checkIsResult(List<Status> statusList, Status status) {
        if (status.nums[0] == 0 && status.nums[1] == 0 && status.nums[2] == 3 && status.nums[3] == 3
            && status.boatStatus == BoatStatus.RIGHT) {
            printResult(statusList);
            ++count;
            return true;
        }
        return false;
    }

    private static void printResult(List<Status> statusList) {
        for (Status status : statusList) {
            System.out.println(status.nums[0] + "," + status.nums[1] + "," + status.nums[2] + "," + status.nums[3]
                               + status.boatStatus.toString());
        }
        System.out.println("---------------");
    }

    /**
     * 校验是否可以移动
     * @param status
     * @param boatAction
     * @return
     */
    private static boolean canMove(Status status, BoatAction boatAction) {
        if (status.boatStatus == boatAction.boatStatus) {
            return false;//当前船的状态与目标状态相同，不需要移动
        }
        for (int i = 0; i < 4; i++) {
            if (status.nums[i] + boatAction.numChanges[i] < 0) {
                return false; //要移动的数量超过最大数量
            }
        }
        return true;
    }

    enum BoatStatus {
        LEFT, RIGHT
    }

    enum BoatAction {

        //一个和尚过河
        ONE_MONK_RIGHT(new int[] { -1, 0, 1, 0 },BoatStatus.RIGHT),
        //一个妖怪过河
        ONE_DEVIL_RIGHT(new int[] { 0, -1, 0, 1 },BoatStatus.RIGHT),
        //一个和尚和一个妖怪过河
        ONE_MONK_ONE_DEVIL_RIGHT(new int[] { -1, -1, 1, 1 },BoatStatus.RIGHT),
        //两个和尚过河
        TOW_MONK_RIGHT(new int[] { -2, 0, 2, 0 },BoatStatus.RIGHT),
        //两个妖怪过河
        TOW_DEVIL_RIGHT(new int[] { 0, -2, 0, 2 },BoatStatus.RIGHT),
        //一个和尚返回
        ONE_MONK_LEFT(new int[] { 1, 0, -1, 0 },BoatStatus.LEFT),
        //一个妖怪返回
        ONE_DEVIL_LEFT(new int[] { 0, 1, 0, -1 },BoatStatus.LEFT),
        //一个和尚和一个妖怪返回
        ONE_MONK_ONE_DEVIL_LEFT(new int[] { 1, 1, -1, -1 },BoatStatus.LEFT),
        //两个和尚返回
        TWO_MONK_LEFT(new int[] { 2, 0, -2, 0 },BoatStatus.LEFT),
        //两个妖怪返回
        TWO_DEVIL_LEFT(new int[] { 0, 2, 0, -2 },BoatStatus.LEFT);

        public int[]      numChanges;
        public BoatStatus boatStatus;

        BoatAction(int[] ints, BoatStatus right) {
            this.numChanges = ints;
            this.boatStatus = right;
        }
    }

    static class Status {
        //初始数量状态
        public int[]      nums       = { 3, 3, 0, 0 };
        public BoatStatus boatStatus = BoatStatus.LEFT;

        public Status(int[] nums, BoatStatus boatStatus) {
            this.boatStatus = boatStatus;
            this.nums = nums;
        }

        public Status() {

        }
    }

}
